#include "backtrackSolution.h"


vector<vector<int>> backtrackSolution::permute(vector<int>& nums)
{
    vector<vector<int>> intResult;

	vector<int> track;
	vector<bool> used(nums.size(), false);
	backtrack(nums, track, used, intResult);
	return intResult;
}

void backtrackSolution::backtrack(vector<int>& nums, vector<int>& track, vector<bool>& used, vector<vector<int>> &intResult)
{
	if (nums.size() == track.size())
	{
		intResult.push_back(track);
		return;
	}

	for (size_t i = 0; i < nums.size(); i++)
	{
		if (used[i]) {
			continue;
		}
		used[i] = true;
		track.push_back(nums[i]);
		backtrack(nums, track, used, intResult);
		track.pop_back();
		used[i] = false;
	}
}

bool isValid(vector<string> &board, int row, int col) {
    int n = board.size();
    for (int i = 0; i < row; ++i) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }
    
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }
    
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

void backtrackNQueens(vector<string> &board, int row, vector<vector<string>> &res){
    if (board.size() == row) {
        res.push_back(board);
        return;
    }
    
    int n = board[row].size();
    for (int col = 0; col < n; ++col) {
        if (!isValid(board, row, col)) {
            continue;
        }
        board[row][col] = 'Q';
        backtrackNQueens(board, row + 1, res);
        board[row][col] = '.';
    }
}

vector<vector<string>> backtrackSolution::solveNQueens(int n) { 
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    backtrackNQueens(board, 0, res);
    return res;
}

void backtrackNQueensTotal(vector<string> &board, int row, int &total){
    if (board.size() == row) {
        ++total;
        return;
    }
    
    int n = board[row].size();
    for (int col = 0; col < n; ++col) {
        if (!isValid(board, row, col)) {
            continue;
        }
        board[row][col] = 'Q';
        backtrackNQueensTotal(board, row + 1, total);
        board[row][col] = '.';
    }
}


int backtrackSolution::totalNQueens(int n) { 
   
    int total = 0;
    vector<string> board(n, string(n, '.'));
    backtrackNQueensTotal(board, 0, total);
    return total;
}

void backtrackSubsets(vector<int> &nums, vector<int> &track, vector<vector<int>> &res, int startIndex) {
    res.push_back(track);
    
    for (int i = startIndex; i < nums.size(); ++i) {
        track.push_back(nums[i]);
        backtrackSubsets(nums, track, res, i + 1);
        track.pop_back();
    }
}

vector<vector<int>> backtrackSolution::subsets(vector<int> &nums) { 
    vector<vector<int>> res;
    vector<int> track;
    backtrackSubsets(nums, track, res, 0);
    return res;
}

void backtrackCombine(int n, int k, vector<int> &track, vector<vector<int>> &res, int startIndex) {
    if (track.size() == k) {
        res.push_back(track);
    }
    
    for (int i = startIndex; i < n; ++i) {
        track.push_back(i + 1);
        backtrackCombine(n, k, track, res, i + 1);
        track.pop_back();
    }
}

vector<vector<int>> backtrackSolution::combine(int n, int k) { 
    vector<vector<int>> res;
    vector<int> track;
    backtrackCombine(n, k, track, res, 0);
    return res;
}

void backtrackSubsetsWithDup(vector<int> &nums, vector<int> &track, vector<vector<int>> &res, int startIndex) {
    res.push_back(track);
    
    for (int i = startIndex; i < nums.size(); ++i) {
        if (i > startIndex && nums[i] == nums[i - 1]) {
            continue;
        }
        track.push_back(nums[i]);
        backtrackSubsetsWithDup(nums, track, res, i + 1);
        track.pop_back();
    }
}


vector<vector<int>> backtrackSolution::subsetsWithDup(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> track;
    backtrackSubsetsWithDup(nums, track, res, 0);
    return res;
}

void backtrackCombinationSum2(vector<int> &nums, vector<int> &track, vector<vector<int>> &res, int startIndex, int target, int trackSum) {
    if (trackSum == target) {
        res.push_back(track);
        return;
    }
    
    if (trackSum > target) {
        return;
    }
    
    for (int i = startIndex; i < nums.size(); ++i) {
        if (i > startIndex && nums[i] == nums[i - 1]) {
            continue;
        }
        track.push_back(nums[i]);
        backtrackCombinationSum2(nums, track, res, i + 1, target, trackSum + nums[i]);
        track.pop_back();
    }
}


vector<vector<int>> backtrackSolution::combinationSum2(vector<int> &candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> track;
    backtrackCombinationSum2(candidates, track, res, 0, target, 0);
    return res;
}

/// <#Description#>
/// - Parameters:
///   - nums: <#nums description#>
///   - track: <#track description#>
///   - used: <#used description#>
///   - intResult: <#intResult description#>
void backtrackPermuteUnique(vector<int>& nums, vector<int>& track, vector<bool>& used, vector<vector<int>> &intResult)
{
    if (nums.size() == track.size())
    {
        intResult.push_back(track);
        return;
    }

    for (size_t i = 0; i < nums.size(); i++)
    {
        if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        
        used[i] = true;
        track.push_back(nums[i]);
        backtrackPermuteUnique(nums, track, used, intResult);
        track.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> backtrackSolution::permuteUnique(vector<int> &nums) { 
    vector<vector<int>> intResult;

    vector<int> track;
    sort(nums.begin(), nums.end());
    vector<bool> used(nums.size(), false);
    backtrackPermuteUnique(nums, track, used, intResult);
    return intResult;
}


void backtrackCombinationSum(vector<int> &nums, vector<int> &track, vector<vector<int>> &res, int startIndex, int target, int trackSum) {
    if (trackSum == target) {
        res.push_back(track);
        return;
    }
    
    if (trackSum > target) {
        return;
    }
    
    for (int i = startIndex; i < nums.size(); ++i) {
        track.push_back(nums[i]);
        backtrackCombinationSum(nums, track, res, i, target, trackSum + nums[i]);
        track.pop_back();
    }
}



vector<vector<int>> backtrackSolution::combinationSum(vector<int> &candidates, int target) {
    vector<vector<int>> res;
    vector<int> track;
    backtrackCombinationSum(candidates, track, res, 0, target, 0);
    return res;
}







